package hot_problems_100;

import java.util.ArrayList;
import java.util.List;

public class P7_0042 {
    public int trap(int[] height) {
        List<Integer> max_heights = new ArrayList<>();
        int last_num = 0;
        int flag = 0;
        for(int i=0; i<height.length; i++){
            if(height[i]>last_num){
                flag = 1;
            } else if(height[i]<last_num){
                if(flag>=0) max_heights.add(i-1);
                flag = -1;
            } else {
                if(flag == 1) max_heights.add(i-1);
                flag = 0;
            }
            last_num = height[i];
        }
        if(flag==1) max_heights.add(height.length-1);
        if(!max_heights.isEmpty() && max_heights.getFirst()==-1) max_heights.removeFirst();
        if(max_heights.size()<2) return 0;
        int left = max_heights.getFirst();
        int right = -1;
        int res = 0;
        int index = 1;
        while(index<max_heights.size()){
            int max_index = index;
            while(index+1 < max_heights.size() &&
                    height[left] > height[max_heights.get(index)]){
                index ++;
                if(height[max_heights.get(max_index)] < height[max_heights.get(index)]){
                    max_index = index;
                }
            }
            right = max_heights.get(max_index);
            int area = 0;
            int max_area_height = Math.min(height[left], height[right]);
            for(int i=left; i<=right; i++){
                if(height[i] >= max_area_height) continue;
                area += max_area_height - height[i];
            }
            res += area;
            left = right;
            index ++;
        }
        return res;
    }

    public static void main(String[] args){
        int[] nums ={8,8,1,5,6,2,5,3,3,9};
        P7_0042 p = new P7_0042();
        System.out.println(p.trap(nums));
    }
}
